/*
* @Author: chenggh
* @Date: 2025-06-13
*/
#include <iostream>
using namespace std;
#define int long long
int v[105], w[105];
// 空间更加优化，变成一维数组(因为状态依赖关系是单向的)
// 没更新之前，代表dp[i - 1] 更新后就是dp[i]
// 但是需要倒过来更新，因为需要保证，更新dp[i][j]的时候dp[i - 1][j - v]没有被更新
int dp[100005] = {0};
int V, n;
int32_t main(){
	cin >> V >> n;
	for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	for(int i = 1; i <= n; i++){
		for(int j = V; j >= 1; j--){
			if(j < v[i]) continue;
			dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	cout << dp[V] << endl;
	return 0;
}
